//
// Created by 紫霄 on 2020/3/29.
//
#include <cmath>
#include <stack>
#include <string>
using namespace std;

#ifndef CPP_DEMO_APPLICATIONSTACK_H
#define CPP_DEMO_APPLICATIONSTACK_H
// 实现进制转换
void convert(stack<char> &S, __int64_t n, __int8_t base) {
  // 新进制下的数位符号
  static char digit[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                         '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
  while (n != 0) {
    S.push(digit[n % base]);
    n /= base;
  }
}
// 实现括号匹配
// 注意这里 针对单种类型的时候，可以使用计数器
// 但是对于多种括号的时候，计数器就很难进行了 比如"（【）】"这样的
bool paren(char *a, size_t beg, size_t end) {
  stack<char> S;
  for (size_t i = 0; i < end; ++i) {
    if (a[i] == '(')
      S.push(a[i]);
    else if (!S.empty())
      S.pop();
    else
      return false;
  }
  return S.empty();
}

//// 栈混洗问题
//简单粗暴法
bool stackMixedWash(int *a, int *c, size_t beg, size_t end) {
  stack<int> A, B, C;
  for (size_t i = end; i > 0; --i) {
    A.push(a[i - 1]);
  }
  for (size_t j = 0; j < end;) {
    if (!A.empty() && A.top() == c[j]) {
      B.push(A.top());
      A.pop();
      C.push(B.top());
      B.pop();
      ++j;
    } else if (!B.empty() && B.top() == c[j]) {
      C.push(B.top());
      B.pop();
      ++j;
    } else {
      if (!A.empty()) {
        B.push(A.top());
        A.pop();
      } else {
        if (!B.empty())
          if (B.top() != c[j]) {
            return false;
          }
      }
    }
  }
  return true;
}
// 与括号匹配问题类似，中转栈的push或者pop操作对应左括号以及右括号
// 实际上 对于合法的栈混洗 与 一个合法括号匹配序列 一一对应

///中缀表达式 实现简单计算器功能

size_t symbolSequenceNumber(char r) {
  switch (r) {
  case '+':
    return 0;
  case '-':
    return 1;
  case '*':
    return 2;
  case '/':
    return 3;
  case '^':
    return 4;
  case '!':
    return 5;
  case '(':
    return 6;
  case ')':
    return 7;
  default:
    return 8;
  }
}

const char orderBetween[9][9] = //运算符优先级表
    {
        /*              |-------------------- 当 前 运 算 符
           --------------------| */
        /*           +    -    *     /    ^    !    (    )    \0
         */
        /* --  + */ {'>', '>', '<', '<', '<', '<', '<', '>', '>'},
        /* |   - */ {'>', '>', '<', '<', '<', '<', '<', '>', '>'},
        /* 栈  * */ {'>', '>', '>', '>', '<', '<', '<', '>', '>'},
        /* 顶  / */ {'>', '>', '>', '>', '<', '<', '<', '>', '>'},
        /* 运  ^ */ {'>', '>', '>', '>', '>', '<', '<', '>', '>'},
        /* 算  ! */ {'>', '>', '>', '>', '>', '>', ' ', '>', '>'},
        /* 符  ( */ {'<', '<', '<', '<', '<', '<', '<', '=', ' '},
        /* |   ) */ {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
        /* -- \0 */ {'<', '<', '<', '<', '<', '<', '<', ' ', '='}

};
bool isdigit(char t) { //判断是否为数字
  if ((t - '0') <= 9 && (t - '0') >= 0)
    return true;
  else {
    return false;
  }
}
float factorial(float t) { //执行阶乘运算
  int num = 1;
  for (int k = 1; k <= t; ++k) {
    num *= k;
  }
  return num;
}
float calcu(float a, char b, float c) { // 执行二目运算
  switch (b) {
  case '+':
    return a + c;
    break;
  case '-':
    return a - c;
    break;
  case '*':
    return a * c;
    break;
  case '/':
    return a / c;
    break;
  case '^':
    return pow(c, a);
    break;
  default:
    exit(-1);
    break;
  }
}
float readNum(char *(&s), stack<float> &num) {
  float theNum = *s - '0';
  ++s;
  if (*s == '.') {
    ++s;
    int i = -1;
    while (isdigit(*s)) {
      theNum = theNum + pow(10, i) * (*s - '0');
      ++s;
      --i;
    }
  } else {
    while (isdigit(*s)) {
      theNum = theNum * 10 + (*s - '0');
      ++s;
    }
  }
  num.push(theNum);
  return num.top();
}
float operation(char *s) { // todo: 实现rpn输出
  stack<char> symbol;
  stack<float> num;
  symbol.push('\0');
  while (!symbol.empty()) {
    if (isdigit(*s)) {
      readNum(s, num);
    } else {
      switch (orderBetween[symbolSequenceNumber(symbol.top())]
                          [symbolSequenceNumber(*s)]) {
      case '>':
        if (symbol.top() == '!') {
          float num_1 = num.top();
          num.pop();
          num.push(factorial(num_1));
        } else {
          float num_1 = num.top();
          num.pop();
          float num_2 = num.top();
          num.pop();
          num.push(calcu(num_1, symbol.top(), num_2));
          symbol.pop();
        }
        break;
      case '<':
        symbol.push(*s);
        ++s;
        break;
      case '=':
        symbol.pop();
        ++s;
        break;
      default:
        exit(-1);
      }
    }
  }
  return num.top();
}
#endif // CPP_DEMO_APPLICATIONSTACK_H
